package leetcode;

public class LC17 {
    public static void main(String[] args) {
        LC17 lc17 = new LC17();
        System.out.println(lc17.firstMissingPositive(new int[]{1}));
        System.out.println(lc17.firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(lc17.firstMissingPositive(new int[]{3,4,-1,1}));
    }
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) nums[i] = nums.length;
        }
        for (int i = 0; i < nums.length; i++) {
           int num = Math.abs(nums[i]);
            if(num <= nums.length)
                nums[num - 1] = -Math.abs(nums[num - 1]);
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) return ++i;
        }
        return nums.length + 1;
    }
}
